1. Technical Field
The present disclosure relates to saturation and, more specifically, to saturating a left shift result using a standard shifter.
2. Description of the Related Art
Digital Signal Processing (DSP) relates to the examination and manipulation of digital representations of electronic signals. Digital signals that are processed using digital signal processing are often digital representations of real-world audio and/or video.
Digital signal processing often involves examining digital signals in the time domain, spatial domain, frequency domain, autocorrelation domain, and/or wavelet domain. Converting a digital signal between domains generally involves rigorous mathematical computations. Once represented in the desired domain, additional mathematical computations may be performed on the digital signals. For example, various filters may be applied to digital signals. Digital signals may also be subjected to various compression/decompression and encryption/decryption algorithms.
Because digital signal processing often deals with digital representations audio and/or video, digital signal processing must often occur in real-time. Mathematical computations must therefore be performed on the digital signals with little or no observable delay. These mathematical computations may be performed by a general purpose computer system such as a desktop computer or workstation or by specialized digital signal processors (also abbreviated DSP).
Digital signal processors are special-purpose microprocessors that have been optimized for the processing of digital signals. Digital signal processors are generally designed to handle digital signals in real-time, for example, by utilizing a real-time operating system (RTOS). A RTOS is an operating system that may appear to handle multiple tasks simultaneously, for example, as the tasks are received. The RTOS generally prioritizes tasks and allows for the interruption of low-priority tasks by high-priority tasks. The RTOS generally manages memory in a way that minimizes the length of time a unit of memory is locked by one particular task and minimizes the size of the unit of memory that is locked; allowing tasks to be performed asynchronously while minimizing the opportunity for multiple tasks to try to access the same block of memory at the same time.
Digital signal processors are commonly used in embedded systems. An embedded system is a specific-purpose computer that is integrated into a larger device. Embedded systems generally utilize a small-footprint RTOS that has been customized for a particular purpose. Digital signal processing is often implemented using embedded systems comprising a digital signal processor and a RTOS.
Digital signals processed by digital signal processors may be represented as a binary series of ones and zeroes. Digital signal processors must therefore be able to handle binary numbers quickly and in high volumes so that the digital signal processors may maintain its real-time character.
While the binary numbering system can easily express positive numbers, expressing negative numbers in binary is more complicated. One method that has been devised for the expression of negative binary numbers is to utilize signed binary numerals. According to this method, a single bit, usually placed before the number, may represent the sign of the number. For example, if the first bit is “1” then the number that follows may be negative while if the first bit is “0” then the number that follows may be positive. For example, the 4-bit number “0010” generally represents the number 2 in standard binary notation. Using signed binary numbers, positive 2 may be expressed as the 5-bit number “00010” where the first digit is the sign bit. Similarly, “10010” may represent negative 2.
This method for expressing negative binary numbers has several disadvantages. For example, there are two different representations for the number zero as both “00000” and “10000” may be taken to have the same value. Additionally, there is the related problem of performing mathematical calculations on signed binary numbers. For example, addition and subtraction are complicated. For example, adding the numbers “00010” (2) with “10010” (−2) using conventional techniques for adding binary numbers would result in the number “10100” (−4). Therefore, when performing arithmetic functions on signed digital numbers, such as calculations commonly performed by digital signal processors, special care must be taken thereby complicating the use of hardware implementing conventional techniques for adding and/or subtracting binary numbers. This special care may decrease performance and/increase expense associated with digital signal processors.
To circumvent the problems associated with signed binary numbers, the two's compliment method is commonly utilized. According to the two's compliment method, the left-most bit of a number, the most significant bit (MSB), may indicate the sign of the number. Where the MSB is zero, the number is positive and where the MSB is one, the number is negative, however unlike the signed binary numbers described above; the MSB is part of the number, affecting both the sign and the value of the expressed number.
According to the two's compliment method, positive numbers may be expressed, for example as in a5-bit number, as “00000” (0) through “01111” (15). While the number may be of any number of bits, the first bit remains as a zero for positive numbers. The value of a positive number according to the two's compliment method is interpreted exactly as it would be in standard binary.
According to the two's compliment method, negative numbers appear as the two's compliment of the corresponding positive number. To calculate the two's compliment, one is added to the one's complement of the number. The one's complement is the inverse of each digit. For example, the one's complement of “00011” (3) is “11100.” Therefore, the two's complement of “00011” (3) is “11101” which has the value of −3.
The two's complement notation has several advantages. For example, zero has only one representation (00000). Additionally, arithmetic functions may be performed on numbers using standard techniques and hardware. For example:
                              00011          ⁢                                          ⁢                      (            3            )                          ⁢                                                                                +            00010                    ⁢                                          ⁢                      (            2            )                          ⁢                                                                    00101          ⁢                                          ⁢                      (            5            )                          ⁢                                      
And for example:
                    00011        ⁢                                  ⁢                  (          3          )                                                                  ⁢                              +            11101                    ⁢                                          ⁢                      (                          -              3                        )                          ⁢                                                          00000        ⁢                                  ⁢                  (          0          )                    
As seen in the example above, where three is added with the negative three, standard arithmetic functions may be performed to arrive at the correct result. However, the correct result depends on the tendency for binary numbers, represented as a fixed number of bits, to drop a digit that should be carried beyond the MSB. This tendency is known as overflow.
While overflow is constructively utilized when performing subtraction, the adding of two large positive operands, for example, may also result in overflow as the MSB takes on a value of 1. In such a case, adding two positive numbers may imprecisely cause the result to rollover into a negative number. To avoid rollover, operations performed in two's complement should be able to detect the overflow and either saturate the result to the most positive or most negative value that may be represented or generate an error.
While saturation does not technically produce the correct result, it produces the result that is as near as possible to the desired result. In the art of digital signal processing, the saturated result is generally preferred to a result that has been rolled over. For example, when adding to the amplitude of a digital signal representing an acoustic wave form such that the new amplitude should be higher than can be expressed, it may be preferable to have the amplitude saturate at the maximum expressible amplitude rather than have the amplitude become a negative value or simply disregarded. Saturation may therefore be an important part of mathematical operations relating to digital signal processing.
One common mathematical operation that may be performed to digital numbers, for example digital signals, is multiplication by powers of two, for example the number may be multiplied by two (21). A number expressed in binary form may be multiplied by two by performing a left shift on the digits of the number. In performing the left shift, each digit is moved to the left by one places and the least significant bit (LSB) may take on a zero value. For example 00011 (3), when shifted to the left by one place becomes 00110 (6), which is equal to 3×2. Left shifting by multiple places may similarly be used to multiply the number by a power of two. For example, left shifting a number by two places produces a multiplication of 22 (4), left shifting a number by three places produces a multiplication of 23 (8), etc.
Left shifting of numbers expressed in two's complement notation may work accurately as long as the bits being shifted out of the number express only zeroes for a positive number or only ones for a negative number and the MSB remains unchanged. However, complications may arise when a one is left shifted either to the MSB or out of the number all together with respect to a positive number or when a zero is left shifter either to the MSB or out of the number all together with respect to a negative number. For example, 01001 (9) left shifted two place results in 00100 (4).
It may therefore be desirable to perform a left shift capable of saturation so that as in the example above, left shifting 01001 (9) would result in the maximum obtainable value 011111 (15) rather than 00100 (4). However, standard hardware shifters using operands expressed in two's compliment notation generally do not support correct saturation after a left shift. It is therefore desirable to utilize hardware that can perform a left shift and be capable of proper saturation.